package com.codingvip.tree;

import com.codingvip.tree.util.TreePrintUtil;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author hansongtao
 */
public class TreeMethod {

    public static void main(String[] args) {
        BinaryTree binaryTree = init();
        //1 按层显示
        levelTraverse(binaryTree.getRoot());
        System.out.println("");
        CodeNode searchNode = new CodeNode(4);
        CodeNode root = binaryTree.getRoot();
        //2.获取父节点
        CodeNode parent = getParent(root, searchNode);
        System.out.println("自己的图型显示:" + parent);
        //3. 图型显示树结构
        TreePrintUtil.pirnt(root);
        //4.前序显示
        preShow(root);
    }

    public static void preShow(CodeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root);
        preShow(root.getLeft());
        preShow(root.getRight());

    }

    /**
     * 初始化
     *
     * @return
     */
    public static BinaryTree init() {
        BinaryTree tree = new BinaryTree();


        CodeNode threetLeft = new CodeNode(6);
        CodeNode threeRight = new CodeNode(7);
        CodeNode fourleft = new CodeNode(8);
        CodeNode fourRight = new CodeNode(9);
        CodeNode twoLeft = new CodeNode(4, fourleft, fourRight);
        CodeNode twotRight = new CodeNode(5);
        CodeNode rootLeft = new CodeNode(2, twoLeft, twotRight);
        CodeNode rootRight = new CodeNode(3, threetLeft, threeRight);
        CodeNode root = new CodeNode(1, rootLeft, rootRight);
        tree.setRoot(root);

        return tree;


    }


    //获取当前结点的父结点
    public static CodeNode getParent(CodeNode root, CodeNode current) {
        return getParentNew(root, current);
    }

    public static CodeNode getParentNew(CodeNode start, CodeNode current) {
        if (start == null) {
            return null;
        }
        if ((start.getLeft() != null && start.getLeft().getData() == current.getData()) ||
                (start.getRight() != null && start.getRight() == current)) {
            return start;
        }
        CodeNode p;
        if ((p = getParentNew(start.getLeft(), current)) != null) {
            return p;
        } else {
            return getParentNew(start.getRight(), current);
        }
    }

    /**
     * 按层显示
     *
     * @param root
     */
    public static void levelTraverse(CodeNode root) {
        Queue<CodeNode> queue = new LinkedList<CodeNode>();
        // 从根节点入队列
        queue.offer(root);
        // 在队列为空前反复迭代
        while (!queue.isEmpty()) {
            // 取出队列首节点
            CodeNode bitNode = queue.poll();
            visitTNode(bitNode);
            if (bitNode.getLeft() != null) {
                // 左孩子入列
                queue.offer(bitNode.getLeft());
            }
            if (bitNode.getRight() != null) {
                // 右孩子入列
                queue.offer(bitNode.getRight());
            }
        }
    }

    /**
     * @param node
     */
    public static void visitTNode(CodeNode node) {
        System.out.print(node.getData() + " ");
    }

}
